package io.gitee.wiqer.hard;

import java.util.Arrays;

/**
 * 描述
 * 给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
 *
 * 数据范围： 1 \le n \le 10^51≤n≤10
 * 5
 *  ，数组中的值满足 1\le val \le 10^81≤val≤10
 * 8
 *
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
 */
public class SolutionNC95_MLS {
    /**
     * 1.排序数组
     * 2.统计连续序列长度：遇到重复元素跳过；遇到不连续元素重置；遇到连续元素加一并更新max
     * @param nums
     * @return
     */
    public int MLS (int[] nums) {
        // write code here
        if (nums == null || nums.length == 0) {
            return 0;
        }

        Arrays.sort(nums);
        int max = 1;
        int continuousLength = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1] + 1) {
                continuousLength++;
                max = Math.max(max, continuousLength);
            } else if (nums[i] == nums[i-1]) {
                continue;
            } else {
                continuousLength = 1;
            }
        }
        return max;
    }
}
